package mySingleList;

//实现不带头结点的单链表
public class MySingleList {

    private static class Node {
        int val;
        Node next;

        Node() {}
        Node(int val) {
            this.val = val;
        }
    }
    Node head; //头指针
    int curSize;
    private boolean isVaild(int index) {  //判断输入下标是否有效
        return index >= 0 && index < curSize;
    }
    public boolean isEmpty() {
        return curSize == 0;
    }
    public int size() {
        return curSize;
    }
    //头插法
    public void addFirst(int val) {
        Node newNode = new Node(val);
        newNode.next = head;
        head = newNode;
        curSize++;
    }
    //尾插法
    public void addLast(int val) {
        Node newNode = new Node(val);
        if (isEmpty()) {
            head = newNode;
        } else {
            Node tmp = head;
            while (tmp.next != null) {
                tmp = tmp.next;
            }
            tmp.next = newNode;
        }
        curSize++;
    }
    //根据下标寻找结点，从0开始
    public Node findByIndex(int index) {
        if (!isVaild(index)) {  //如果查询的下标小于0或者大于等于当前长度，则无效
            throw new MySingleListException("下标输入有误");
        }
        Node tmp = head;
        for (int i = 0; i < index; i++, tmp = tmp.next) {
            ;
        }
        return tmp;
    }
    //根据数据寻找结点
    public Node findByVal(int val) {
        Node tmp = this.head;
        while (tmp != null) {
            if (tmp.val == val) {
                return tmp;
            }
            tmp = tmp.next;
        }
        return null;
    }
    //在下标处插入结点
    public void insertByIndex(int index, int val) {
        if (!isVaild(index)) {
            throw new MySingleListException("插入结点所输入的下标不合法");
        }
        if (index == 0) {
            addFirst(val);
            curSize++;
            return;
        }
        if (index == curSize) {
            addLast(val);
            curSize++;
            return;
        }
        Node newNode = new Node(val);
        Node prev = findByIndex(index - 1); //要找到这个索引前面那个结点
        newNode.next = prev.next;
        prev.next = newNode;
        curSize++;
    }
    //删除第一次遇到的val结点
    public Node remove(int val) {
        if (isEmpty() || curSize == 1 && head.val == val) {
            return head;
        }
        if (head.val == val) {
            Node ret = head;
            head = head.next;
            curSize++;
            return ret;
        }
        Node tmp = this.head;
        boolean flg = false;
        while (tmp.next != null) {
            if (tmp.next.val == val) {
                flg = true;
                curSize--;
                break;
            }
            tmp = tmp.next;
        }
        Node ret = tmp.next;
        if (flg) {
            tmp.next = tmp.next.next;
        }
        return ret;
    }
    public void display() {
        Node tmp = this.head;
        while (tmp != null) {
            System.out.print(tmp.val + " ");
            tmp = tmp.next;
        }
        System.out.println();
    }

    //删除所有值为val的节点
    public void removeAllVal(int val) {
        while (head != null && head.val == val) {
            head = head.next;
        }
        if (head != null) {
            Node tmp = head;
            while (tmp.next != null) {
                if (tmp.next.val == val) {
                    tmp.next = tmp.next.next;
                    curSize--;
                } else {
                    tmp = tmp.next;
                }
            }
        }
    }
    public static void main(String[] args) {
        MySingleList mySingleList = new MySingleList();
        mySingleList.addFirst(1);
        mySingleList.addFirst(2);
        mySingleList.addFirst(3);
        mySingleList.addFirst(3);
        mySingleList.addFirst(3);
        mySingleList.addFirst(3);
        mySingleList.addFirst(4);
        mySingleList.removeAllVal(3);

        mySingleList.display();
        System.out.println(mySingleList.size());
    }
}
